In article <3nn9gp$nj0@ixnews2.ix.netcom.com> plugg@ix.netcom.com (Sandra Desmond) writes:

>Cool! Maybe we'll be able to figure out how Michael Abrash managed to
>get all of Quake's divides for free!

>In any case it'll certainly help improve the signal-to-noise ratio here
>;)

>Cheers,

>Mark Feldman

Hello Mr. Feldman.

I have already proposed this solution many times in this newsgroup, but I'll 
reiterate as it seem to have evaded everyone's memory. My personnal opinion of 
it is it's not worth it, but here goes anyhow.

Say the constant-z lines are within 45 degrees of being vertical (the 
algorithm can be tweaked to work with any angle, either by using a reflection 
or by really tweaking it, but I won't discuss this). For example, here are the 
constant-z lines:

abcdefg
abcdefg
bcdefgh
bcdefgh
bcdefgh
cdefghi
cdefghi
defghij
defghij
defghij
efghijk

etc...

Now look at a horizontal scan-line. You intersect exactly one constant-z line 
per pixel. The first horizontal line looks like this:

abcdefg

If we were to have a wider screen to the right, we would also have the 
constant-z lines h,i,j and k. Example:

abcdefghijk

Now, calculate the real texture coordinate for all these pixels. You now know 
the true texture coordinate for all pixels of all constant-z lines for the 
first horizontal-line.

As you go to the second horizontal line, you can incrementally find the new 
texture coordinates of these constant-z lines, them being constant-z that is.

Thus, for each horizontal line, you can incrementally calculate the new 
texture coordinate of all constant-z lines.

What we do is generate the spans with a conventional horizontal scan-line 
algorithm and only draw the relevant pixels (while we still possibly 
incrementally calculate more than the relevant pixels).

Thus, if the polygon to draw is:
   d 
  cde
 cdef
bcdefg
  defg
    ghi
      i

We initially need to calculate the true texture coordinate of the topmost 
pixel, then for all pixels on the "d" constant-z line, the calculations can be 
performed incrementally. On the second horizontal scanline, we need to 
calculate the true texture coordinates for the pixel in the c and e constant-z 
lines, but then we can calculate all of the texture coordinates on constant-z 
lines "c", "d" and "e" incrementally. On the next horizontal scanline, we need 
to calculate the true texture coordinate of the "f" scanline, but thereafter 
we can calculate it incrementally. Etc...

The advantages are nearly the same as the straight constant-z polygon drawing 
algorithm. The disadvantages however, are a bit different. It will not be as 
fast, involving one more lookup per pixel. The algorithm is also much more 
complicated and difficult to implant. However, we removed the aliasing from 
the polygon's edges (e.g. the outline will be correct in the sense that it 
will be exactly the same one as when generated with a horizontal scan-line 
algorithm).

I know this algorithm is not discussed at all in Zed3D, but there are so many 
things that need adding in Zed3D that I am not totally certain that I will be 
able to add this particular one (since I am going on a 3 week trip very soon). 
As a matter of fact, I'm going to copy and paste this article as is in Zed3D 
now that I think of it.

Wish you the best of lucks, and may this help you.

Sebastien Loisel